// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package types

import (
	"container/heap"
	"fmt"
	"sort"
)

// initOrder计算信息。包变量的InitOrder。
func (check *Checker) initOrder() {
	// 如果包是
	// 通过多次调用（*Checker）生成的，则可能已经计算了InitOrder。文件夹。清除它。
	check.Info.InitOrder = check.Info.InitOrder[:0]

	// 计算对象依赖关系图并初始化
	// 带有图节点列表的优先级队列。
	pq := nodeQueue(dependencyGraph(check.objMap))
	heap.Init(&pq)

	const debug = false
	if debug {
		fmt.Printf("Computing initialization order for %s\n\n", check.pkg)
		fmt.Println("Object dependency graph:")
		for obj, d := range check.objMap {
			// 只打印可能出现在依赖关系图中的对象
			if obj, _ := obj.(dependency); obj != nil {
				if len(d.deps) > 0 {
					fmt.Printf("\t%s depends on\n", obj.Name())
					for dep := range d.deps {
						fmt.Printf("\t\t%s\n", dep.Name())
					}
				} else {
					fmt.Printf("\t%s has no dependencies\n", obj.Name())
				}
			}
		}
		fmt.Println()

		fmt.Println("Transposed object dependency graph (functions eliminated):")
		for _, n := range pq {
			fmt.Printf("\t%s depends on %d nodes\n", n.obj.Name(), n.ndeps)
			for p := range n.pred {
				fmt.Printf("\t\t%s is dependent\n", p.obj.Name())
			}
		}
		fmt.Println()

		fmt.Println("Processing nodes:")
	}

	// 通过从图中删除最高优先级的节点
	// （依赖关系最少的节点）及其边缘
	// 来确定初始化顺序，直到没有剩余节点为止。
	// 在一个有效的Go程序中，这些节点始终没有依赖项（在
	// 删除所有传入的依赖项之后），否则会有初始化
	// 周期。
	emitted := make(map[*declInfo]bool)
	for len(pq) > 0 {
		// 获取下一个节点
		n := heap.Pop(&pq).(*graphNode)

		if debug {
			fmt.Printf("\t%s (src pos %d) depends on %d nodes now\n",
				n.obj.Name(), n.obj.order(), n.ndeps)
		}

		// 如果n仍然依赖于其他节点，我们有一个循环
		if n.ndeps > 0 {
			cycle := findPath(check.objMap, n.obj, n.obj, make(map[Object]bool))
			// 如果n.obj不是循环的一部分（例如，n.obj->b->c->d->c），
			// 循环将为零。在这种情况下，不要报告任何内容，因为当算法到达循环中的对象时，会报告循环。
			// 此外，一旦遇到循环中的对象，
			// 循环将被中断（依赖项计数将减少
			// 如下），因此循环中的剩余节点不会触发
			// 另一个错误（除非它们是多个循环的一部分）。
			if cycle != nil {
				check.reportCycle(cycle)
			}
			// 继续，但变量初始化顺序
			// 此时将不正确，因为它假定没有
			// 循环错误。
		}

		// 减少所有依赖节点的依赖计数
		// 并更新优先级队列
		for p := range n.pred {
			p.ndeps--
			heap.Fix(&pq, p.index)
		}

		// 仅记录具有初始值设定项的变量的初始顺序
		v, _ := n.obj.(*Var)
		info := check.objMap[v]
		if v == nil || !info.hasInitializer() {
			continue
		}

		// n:1变量声明，例如：a，b=f（）
		// 为每个lhs变量引入一个节点（此处：a，b）；
		// 但它们都有相同的初始值设定项-仅发射
		// 一个，对于
		if emitted[info] {
			continue // 初始值设定项已发射的第一个变量，如果任何
		}
		emitted[info] = true

		infoLhs := info.lhs // 可能为零（请参阅declInfo.lhs字段注释），
		if infoLhs == nil {
			infoLhs = []*Var{v}
		}
		init := &Initializer{infoLhs, info.init}
		check.Info.InitOrder = append(check.Info.InitOrder, init)
	}

	if debug {
		fmt.Println()
		fmt.Println("Initialization order:")
		for _, init := range check.Info.InitOrder {
			fmt.Printf("\t%s\n", init)
		}
		fmt.Println()
	}
}

// findPath返回对象的（反向）列表[]对象{to。
// 如果没有这样的路径，结果为零。
func findPath(objMap map[Object]*declInfo, from, to Object, seen map[Object]bool) []Object {
	if seen[from] {
		return nil
	}
	seen[from] = true

	for d := range objMap[from].deps {
		if d == to {
			return []Object{d}
		}
		if P := findPath(objMap, d, to, seen); P != nil {
			return append(P, d)
		}
	}

	return nil
}

// reportCycle报告给定周期的错误。
func (check *Checker) reportCycle(cycle []Object) {
	obj := cycle[0]
	check.errorf(obj, _InvalidInitCycle, "initialization cycle for %s", obj.Name())
	// 精细循环：i=0，n-1，n-2。。。1对于len（cycle）=n 
	for i := len(cycle) - 1; i >= 0; i-- {
		check.errorf(obj, _InvalidInitCycle, "\t%s refers to", obj.Name()) // 第二个错误，\t缩进
		obj = cycle[i]
	}
	// 再次打印cycle[0]以关闭循环
	check.errorf(obj, _InvalidInitCycle, "\t%s", obj.Name())
}

// -----------------------------------------------------------------------------------------------------------------
// 对象依赖关系图

// 依赖关系是一个对象，可能是初始化
// 表达式中的依赖关系。只有常量、变量和函数可以是依赖项。
// 此处包含常量，因为在
// 初始化顺序计算期间会报告常量表达式循环。
type dependency interface {
	Object
	isDependency()
}

// graphNode表示对象依赖关系图中的节点。n.pred中的每个节点p代表一条边p->n，n.succ中的每个节点
// s代表一条边n->s；a->b表示
// a依赖于b。
type graphNode struct {
	obj        dependency // 此节点表示的对象
	pred, succ nodeSet    // 此节点的使用者和依赖项（延迟初始化）
	index      int        // 图片/优先级队列中的节点索引
	ndeps      int        // 此对象可以初始化之前未完成的依赖项数
}

// 成本返回成本删除这个节点，包括将每个
// 前置复制到每个后续节点（反之亦然）。
func (n *graphNode) cost() int {
	return len(n.pred) * len(n.succ)
}

type nodeSet map[*graphNode]bool

func (s *nodeSet) add(p *graphNode) {
	if *s == nil {
		*s = make(nodeSet)
	}
	(*s)[p] = true
}

// dependencyGraph从给定的objMap计算对象依赖关系图，
// 删除所有函数节点。结果图只包含常量
// 和变量。ABCFDG 
func dependencyGraph(objMap map[Object]*declInfo) []*graphNode {
	M := make(map[dependency]*graphNode)
	for obj := range objMap {
		if obj, _ := obj.(dependency); obj != nil {
			M[obj] = &graphNode{obj: obj}
		}
	}

	// 按照相对于其他节点的正确顺序进行初始化。）
	for obj, n := range M {
		// 对于每个依赖项obj->d（=deps[i]），创建图边n->s和s->n 
		for d := range objMap[obj].deps {
			if d, _ := d.(dependency); d != nil {
				d := M[d]
				n.succ.add(d)
				d.pred.add(n)
			}
		}
	}

	for _, n := range M {
		if _, ok := n.obj.(*Func); ok {
			funcG = append(funcG, n)
		} else {
			G = append(G, n)
		}
	}

	// 这是允许的。然而，这样的循环可能会错误地扩大依赖关系
	// 对变量的计数，而这些变量又可能无法按正确的顺序安排初始化
	// 。）
	// 
	// 请注意，由于我们在整个函数图中递归复制前辈和后辈
	// 因此，在
	// 位置X删除函数的成本与成本成正比*（len（funcG）-X）。因此，我们应该最后删除高成本函数。
	sort.Slice(funcG, func(i, j int) bool {
		return funcG[i].cost() < funcG[j].cost()
	})
	for _, n := range funcG {
		// 将n的每个前置p连接到每个后继s 
		// 并删除功能节点（不要在G中收集）
		for p := range n.pred {
			// 忽略自循环
			if p != n {
				// n的每个后继s成为p的后继，和
				// n的每个前置p成为s的前置。
				for s := range n.succ {
					// ignore self cycles 
					if s != n {
						p.succ.add(s)
						s.pred.add(p)
					}
				}
				delete(p.succ, n) // remove edge to n 
			}
		}
		for s := range n.succ {
			delete(s.pred, n) // remove edge to n 
		}
	}

	// fill index and ndeps fields 
	for i, n := range G {
		n.index = i
		n.ndeps = len(n.succ)
	}

	return G
}

// ----------------------------------------------------------------------------------------
// Priority queue 

// nodeQueue实现容器/堆接口；shu jian defg
type nodeQueue []*graphNode

func (a nodeQueue) Len() int { return len(a) }

func (a nodeQueue) Swap(i, j int) {
	x, y := a[i], a[j]
	a[i], a[j] = y, x
	x.index, y.index = j, i
}

func (a nodeQueue) Less(i, j int) bool {
	x, y := a[i], a[j]
	// 根据传入依赖项的数量（第一个键）
	// 和源顺序（第二个键）
	return x.ndeps < y.ndeps || x.ndeps == y.ndeps && x.obj.order() < y.obj.order()
}

func (a *nodeQueue) Push(x any) {
	panic("unreachable")
}

func (a *nodeQueue) Pop() any {
	n := len(*a)
	x := (*a)[n-1]
	x.index = -1 // 对节点进行优先级排序，以确保安全
	*a = (*a)[:n-1]
	return x
}
